package algorithm.dynamicProgramming.p198;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 */
class Solution_v2 {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        // 抢劫[nums.length - 1...nums.length - 1]这个范围内的房子的最高金额为nums[nums.length - 1]
        memo[n - 1] = nums[n - 1];
        // 计算抢劫[i...nums.length - 1]范围内的房子的最高金额
        // 确定抢劫第 i 间房子
        for (int i = n - 2; i >= 0; i--) {
            // 从计算抢劫[i...nums.length - 1]范围内的房子的最高金额
            for (int j = i; j < n; j++) {
                memo[i] = Math.max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0));
            }
        }
        return memo[0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v2().rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(new Solution_v2().rob(new int[]{1, 2, 3, 1}));
    }
}